#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<time.h>
int QuickSort(int* arr, int begin, int end)
{
	int key = arr[begin];
	int pit = begin;
	while (begin < end)
	{
		while (begin<end && arr[end]>key)
		{
			--end;
		}
		arr[pit] = arr[end];
		pit = end;
		while (begin < end && arr[begin] < key)
		{
			++begin;
		}
		arr[pit] = arr[begin];
		pit = begin;
	}
	arr[pit] = key;
	return pit;
}
int QuickSort(int* arr, int begin, int end)
{
	int key = arr[begin];
	int pit = begin;
	while (begin < end)
	{
		while (begin < end && arr[end] >= key)
		{
			--end;
		}
		arr[pit] = arr[end];
		pit = end;
		while (begin < end && arr[begin] <= key)
		{
			++begin;
		}
		arr[pit] = arr[begin];
		pit = begin;
	}
	arr[pit] = key;
	return pit;
}
int QuickSort(int* arr, int begin, int end)
{
	int key = arr[begin];
	int pit = begin;
	while (begin < end)
	{
		while (begin<end && arr[end]>=arr[key])
		{
			--end;
		}
		arr[pit] = arr[end];
		pit = end;
		while (begin < end && arr[begin] < arr[key])
		{
			++begin;
		}
		arr[pit] = arr[begin];
		pit = begin;
	}
	arr[pit] = key;
	return pit;
}